package com.practice.niuke.new_direct_practice.class05;

/**
 * 设计并实现TopKRecord结构， 可以不断地向其中加入字符串， 并且可以根据字符串出现的情况
 * 随时打印加入次数最多的前k个字符串。 具体为:
 * 1)k在TopKRecord实例生成时指定， 并且不再变化(k是构造TopKRecord的参数)
 * 2)含有 add(String str)方法， 即向TopKRecord中加入字符串
 * 3)含有printTopK()方法， 即打印加入次数最多的前k个字符串， 打印有哪些 字符串和对应的次
 * 数即可， 不要求严格按排名顺序打印。
 * 4)如果在出现次数最多的前k个字符串中， 最后一名的字符串有多个， 比如出现次数最多的前3
 * 个字符串具体排名为:
 * A 100次 B 90次 C 80次 D 80次 E 80次， 其他任何字符串出现次数都不超过80次
 * 那么只需要打印3个， 打印ABC、 ABD、 ABE都可以。 也就是说可以随意抛弃最后一名， 只要求打
 * 印k个
 * 要求:
 * 1)在任何时候， add 方法的时间复杂度不超过O(logk)
 * 2)在任何时候， printTopK方法的时间复杂度不超过O(k)。
 */
import java.util.HashMap;

public class Code04_TopKTimesRealTime {

	/**
	 * 堆中的节点元素定义
	 */
	public static class Node {
		/**
		 * 字符串
		 */
		public String str;
		/**
		 * 字符串出现的次数
		 */
		public int times;

		public Node(String s, int t) {
			str = s;
			times = t;
		}
	}

	public static class TopKRecord {
		// 堆
		private Node[] heap;
		// 堆的size
		private int heapSize;
		// 词频表 string -> Node(times)
		private HashMap<String, Node> strNodeMap;
		// 堆位置表
		private HashMap<Node, Integer> nodeIndexMap;

		public TopKRecord(int K) {
			heap = new Node[K];
			heapSize = 0;
			strNodeMap = new HashMap<String, Node>();
			nodeIndexMap = new HashMap<Node, Integer>();
		}

		/**
		 * str为用户现在给的字符串
		 * @param str
		 */
		public void add(String str) {
			Node curNode = null;
			int preIndex = -1; // str之前在堆上的位置
			// 查词频表，看看有没有关于这条str的记录
			if (!strNodeMap.containsKey(str)) {
				// 生成一个新Node
				curNode = new Node(str, 1);
				// 在词频表中加入当前这个（str，Node）记录
				strNodeMap.put(str, curNode);
				// 当前这个str对应的Node在堆中的位置设置为-1
				nodeIndexMap.put(curNode, -1);
			} else {// str之前进来过
				// 查出当前在词频表中的记录的Node
				curNode = strNodeMap.get(str);
				// 将查出的Node的times++
				curNode.times++;
				// 在堆位置表中查出当前这个Node在堆数组中的索引位置
				preIndex = nodeIndexMap.get(curNode);
			}
			
			if (preIndex == -1) { // 当前用户给的str所指向的Node不在堆上
				if (heapSize == heap.length) { // 堆满了
					// 用户当前所给str所代表的Node的times > 堆顶Node的times，
					if (heap[0].times < curNode.times) {
						// 在堆位置表中，将堆顶Node元素所对应的位置改为-1
						nodeIndexMap.put(heap[0], -1);
						// 在堆位置表中，将当前所给str所代表的Node元素所对应的位置改为0（堆顶位置）
						nodeIndexMap.put(curNode, 0);
						// 将堆顶Node元素改为，当前所给str所代表的Node元素
						heap[0] = curNode;
						// 从堆顶到堆结束位置，对堆进行Heapify调整
						heapify(0, heapSize);
					}
				} else {// 堆没有满
					// 在堆位置表中，将当前所给str所代表的Node元素所对应的位置改为堆结束位置（队尾）
					nodeIndexMap.put(curNode, heapSize);
					// 将队尾设置为当前所给str所代表的Node元素
					heap[heapSize] = curNode;
					// 将队尾设置为当前所给str所代表的Node元素后进行HeapInsert过程
					heapInsert(heapSize++);
				}
			} else { // 当前用户给的str所指向的Node已经在堆上了
				// 从当前str所指向的Node在堆中的位置开始，到堆中最后的位置部分，进行heapify调整
				heapify(preIndex, heapSize);
			}
		}

		public void printTopK() {
			System.out.println("TOP: ");
			for (int i = 0; i != heap.length; i++) {
				if (heap[i] == null) {
					break;
				}
				System.out.print("Str: " + heap[i].str);
				System.out.println(" Times: " + heap[i].times);
			}
		}

		private void heapInsert(int index) {
			while (index != 0) {
				int parent = (index - 1) / 2;
				if (heap[index].times < heap[parent].times) {
					swap(parent, index);
					index = parent;
				} else {
					break;
				}
			}
		}

		private void heapify(int index, int heapSize) {
			int l = index * 2 + 1;
			int r = index * 2 + 2;
			int smallest = index;
			while (l < heapSize) {
				if (heap[l].times < heap[index].times) {
					smallest = l;
				}
				if (r < heapSize && heap[r].times < heap[smallest].times) {
					smallest = r;
				}
				if (smallest != index) {
					swap(smallest, index);
				} else {
					break;
				}
				index = smallest;
				l = index * 2 + 1;
				r = index * 2 + 2;
			}
		}

		private void swap(int index1, int index2) {
			nodeIndexMap.put(heap[index1], index2);
			nodeIndexMap.put(heap[index2], index1);
			Node tmp = heap[index1];
			heap[index1] = heap[index2];
			heap[index2] = tmp;
		}

	}

	public static String[] generateRandomArray(int len, int max) {
		String[] res = new String[len];
		for (int i = 0; i != len; i++) {
			res[i] = String.valueOf((int) (Math.random() * (max + 1)));
		}
		return res;
	}

	public static void printArray(String[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		TopKRecord record = new TopKRecord(2);
		record.add("zuo");
		record.printTopK();
		record.add("cheng");
		record.add("cheng");
		record.printTopK();
		record.add("Yun");
		record.add("Yun");
		record.printTopK();

	}
}